#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Node {
   public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 1, 2, 3, 4, 5, 6, 8, 9, 10, 12
class Solution {
    int minThree(int i, int j, int k) {
        if (i <= j && i <= k)
            return i;
        if (j <= i && j <= k)
            return j;
        if (k <= i && k <= j)
            return k;
        return i;
    }

   public:
    int nthUglyNumber(int n) {
        vector<int> result(n, 0);
        result[0] = 1;
        int i1 = 0, i2 = 0, i3 = 0;
        for (int i = 1; i < n; i++) {
            int tmp = minThree(result[i1] * 2, result[i2] * 3, result[i3] * 5);
            if (result[i1] * 2 == tmp)
                i1++;
            if (result[i2] * 3 == tmp)
                i2++;
            if (result[i3] * 5 == tmp)
                i3++;
            result[i] = tmp;
        }
        return result[n - 1];
    }
};

int main() {
    int i = Solution().nthUglyNumber(100);
    printf("输出:%d\n", i);
    return 0;
}
